package com.nanbei.backyracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassDescription: 数组中和 leetCode39
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/12 16:44
 */
public class CombinationSum {

    public static void main(String[] args) {
        List<List<Integer>> combine = combinationSum(new int[]{8,7,4,3}, 11);
        System.out.println(combine);
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {


        List<List<Integer>> coll = new ArrayList<>();
        LinkedList<Integer> stack = new LinkedList<>();
        sf(coll, stack, candidates, 0, target,0);
        return coll;
    }

    private static void sf(List<List<Integer>> coll, LinkedList<Integer> stack, int[] candidates, int index, int target,int sum) {
        // 当栈中的元素数量等于数组长度时，表示找到了一种排列

        if (sum == target) {
            coll.add(new ArrayList<>(stack));
            return;
        }

        for (int i = index; i < candidates.length; i++) {

            //减枝操作
            if (target-sum  < candidates[i] ){
                continue;
            }

            // 将该数字加入栈中
            stack.push(candidates[i]);
            sum +=candidates[i];
            // 递归调用后面的数字
            sf(coll,stack,candidates,i,target,sum);
            // 回溯：将该数字移出栈
            sum-=candidates[i];
            stack.pop();


        }

    }
}
